package code_rhapsody.array;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @author Synhard
 * @version 1.0
 * @class Code9
 * @description 844. 比较含退格的字符串
 * 给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
 *
 * 注意：如果对空文本输入退格字符，文本继续为空。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：S = "ab#c", T = "ad#c"
 * 输出：true
 * 解释：S 和 T 都会变成 “ac”。
 * 示例 2：
 *
 * 输入：S = "ab##", T = "c#d#"
 * 输出：true
 * 解释：S 和 T 都会变成 “”。
 * 示例 3：
 *
 * 输入：S = "a##c", T = "#a#c"
 * 输出：true
 * 解释：S 和 T 都会变成 “c”。
 * 示例 4：
 *
 * 输入：S = "a#c", T = "b"
 * 输出：false
 * 解释：S 会变成 “c”，但 T 仍然是 “b”。
 *  
 *
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-07-23 8:17
 */
public class Code9 {
    public static void main(String[] args) {
        System.out.println(backspaceCompare("ab#c", "ad#c"));
    }

    public static boolean backspaceCompare(String s, String t) {
        Deque<Character> stack = new LinkedList<>();
        StringBuilder sb1 = new StringBuilder(), sb2 = new StringBuilder();
        char temp;
        for (int i = 0; i < s.length(); i++) {
            temp = s.charAt(i);
            if (temp == '#') {
                if (!stack.isEmpty()) {
                    stack.removeFirst();
                }
                continue;
            }
            stack.addFirst(temp);
        }
        while (!stack.isEmpty()) {
            sb1.append(stack.removeFirst());
        }

        for (int i = 0; i < t.length(); i++) {
            temp = t.charAt(i);
            if (temp == '#') {
                if (!stack.isEmpty()) {
                    stack.removeFirst();
                }
                continue;
            }
            stack.addFirst(temp);
        }
        while (!stack.isEmpty()) {
            sb2.append(stack.removeFirst());
        }

        return sb1.toString().equals(sb2.toString());
    }
}
/*
栈模拟
 */